1. Field of the Invention
This invention relates generally to color image display systems, and more particularly to digital color image display systems used with a frame buffer.
2. Description of the Prior Art
Traditionally, digital color images are composed a large number of array of individual pixels. Each pixel in the color image associates with position information indicating its position in the array, and color information including three basic colors (red, green and blue) so that the composite of the three basic colors attains the desired color for the pixel. Typically, each basic color in a pixel is 8 bits (1 byte) long, and each pixel in the color image has 24 bits. The color information for all pixels is stored in a digital memory device.
Referring to FIG. 1, there is shown a typical digital color display system 10 which includes a color image transducer 12 (video camera, scanner or facsimile), an image processor 14, a memory device 16, a frame buffer 18 and a displayer 24. The image processor is responsible for controlling the color image transducer, the memory storage, the frame buffer and the displayer, and to process the imaging information. In the process of color imaging, color image transducer 12 converts desired color images into pixels arranged in an array format. Typically, the color image transducer generates approximately 8 mega pixels for a 8.5.times.11 color image at 300 dots per inch (dpi) density. The color information for the pixels are then stored into memory device 16. Because each pixel has three basic colors with each color having 8 bits, approximately 24 mega bytes memory size is needed to store the color information for all pixels. Image processor 14 processes the color information stored in memory device 16 and feeds the processed color information into frame buffer 18. The frame buffer includes a color table 20 and an index memory 22. The color table stores the color combinations for the color image, and the index memory stores the color table and the position information for each pixel. Finally, each of the pixels is displayed at a specific position on displayer 24 according to the color information stored in color table 20 for a color image.
Theoretically, in a color image, each pixel has 16 (2.sup.24) million possible combinations of full colors; in other words, the 16 million possible combinations of full colors form a color space, and the color of any individual pixel in the color image is distributed within the color space. Thus, for a specific image, the color of all pixels in the color image has a specific distribution pattern in the color space. However, in practice, fewer colors are selected to display the color image to considerations such as cost, memory size restriction and speed. In typical frame buffers available in the present market, the color table has a memory with a size of 256 cells for storing selected colors. Thus, in order to use a typical frame buffer to display a full color image, it is necessary to select 256 colors from the color image and map the 16 million possible combinations of full colors into the 256 colors for all pixels stored in memory storage 10. Such selecting and mapping process are called color quantization.
There are several algorithms to select the 256 colors from the color image to be displayed. Generally speaking, the desired criteria of the color selection method are: 1) preserving originality of the color image; 2) having high speed; 3) being easy to be implemented on hardware; and 4) being adaptable to expansion.
One of the algorithms uses a predefined color table which statistically is the most popular colors to represent a color image. The disadvantage of this algorithm is that the color table does not depend on the color distribution of the image itself. For example, if the color image has a lot of red elements, the predefined color table cannot be able to reflect more redness in the color table.
Another algorithm called Medium Cut algorithm subdivides color space for a color image into smaller and smaller rectangular boxes. The division algorithm is based on cutting the boxes along the medium point so that equal number of pixels falls on each side. As a result, each box contains the same number of pixels. One of the disadvantages of this algorithm is that it takes time to calculate the medium point in each division, thus reducing the speed.
Another algorithm divides the color space for a color image into 64 uniform cells. It then calculates an axis with the highest variance in each of the 64 cells. The 32 cells with the largest variance are divided into 2 along the axis with the largest variance. Variance, a mathematical term, is used to measure the degree of changes in a set of samples. So a cell with larger variance means that there is a more uneven distribution of colors in the cell. By dividing cells with the largest variance, the color image can be more accurately represented. This process is repeated 6 times to generate 256 cells in the color space. The disadvantage of this algorithm is the first 64 cells are created independent of the color distribution of the image. Moreover, calculating the variance is even more time-consuming than calculating the medium value. Furthermore, more complicated algorithm may involve higher hardware cost.
Thus, there is a need for a fast color quantization algorithm which has the features of easy hardware implementation, adaptability to expand and preserve originality of the color image.